1. Field of the Invention
The present invention relates to data communications, in particular, to cyclic redundancy check (CRC) computations in a communications processor.
2. Description of the Related Art
Cyclic Redundancy Check (CRC) is an error-detecting code that is commonly used in data communication systems. The CRC error-detecting method employs polynomial computations using arithmetic of finite fields. A frame check sequence (FCS) refers to the result of the CRC algorithm computation that is used and added to a frame in Ethernet/Data link layer and other communication protocols. The FCS is appended to the end of the data transmission to check for errors introduced in the communications channel. The CRC function used in Ethernet is described in the Institute of Electrical and Electronic Engineers (IEEE) Standard 802.3-2008 (herein, “IEEE 802.3”).
In general, as described in 3.2.9 of IEEE 802.3, the FCS field in Ethernet contains a 4-octet (32-bit) CRC value. The value is computed as a CRC function of the contents of the protected fields of the MAC frame: destination address, source address, length/type field, MAC client data, and Pad. The encoding is defined by a 32 degree generating polynomial.
The algorithm of the 32-bit FCS computation from IEEE 802.3 can be rewritten so that the input data is represented as a sequence of bytes (b1, b2, bN), where N represents the final byte index. Each byte has a corresponding 32-bit state vector, and the final state vector sN is complemented to produce the FCS, or CRC value. Each state vector is computed with its preceding state vector using the following formula: si+1=(si×M)+(bi×M*), where i represents the integer index value, M is a given 32×32 matrix, and M* is an 8×32 sub-matrix of M. In the formula s0 is a given 32-bit constant (e.g., IEEE 802.3 uses the constant where all 32 bits are equal to 1). Further, in this formula and throughout the specification when applied to binary operations with matrices and/or vectors, “+” denotes bitwise addition (bitwise exclusive-or operation) and “×” denotes multiplication of vectors and/or matrices using modulo 2 arithmetic. Operators “+” and “×” have their standard arithmetical meaning, for example, when they are applied to serial numbers of variables or dimensions of matrices.
FCS computations are implemented in software, hardware, or a combination of software and hardware. Often, hardware modules that compute CRC values require input data blocks with a fixed number of bytes. Existing implementations for hardware-approach computations inefficiently increase the gate count in order to perform FCS computations on a variable number of input bytes.